package codeRandomThoughts.Test647回文子串;

public class Solution2 {
    public int countSubstrings(String s) {
        int count = 0;
        //dp[i][j]:下标从i-j的子串中回文子串的数目
        boolean[][] dp = new boolean[s.length()][s.length()];

        //初始化 全为false

        //递推
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = 0; j < s.length(); j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i <= 1) {
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                    }
                }
                if (dp[i][j]) count++;
            }
        }

        return count;
    }
}
